The present invention relates to information processing systems and methods. More particularly, the present invention is directed to methods and/or apparatus relating to converting data encoded in a numerical format to character code type data.
Pursuant to 37 C.F.R. 1.71(e), Applicants note that a portion of this disclosure contains material that is subject to and for which is claimed copyright protection (such as, but not limited to, source code listings, screen shots, user interfaces, or user instructions, or any other aspects of this submission for which copyright protection is or may be available in any jurisdiction.). The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or patent disclosure, as it appears in the Patent and Trademark Office patent file or records. All other rights are reserved, and all other reproduction, distribution, creation of derivative works based on the contents, public display, and public performance of the application or any part thereof are prohibited by applicable copyright law.
This application is being filed with paper appendices totaling 43 pages. These appendices and all other papers filed herewith, including papers filed in any attached Information Disclosure Statement (IDS), are incorporated herein by reference. The appendix contains further examples of source code listings and information related to various embodiments of the invention at various stages of development.
A task that faced the early designers of computer architecture was how to quickly and efficiently display numerical data. Numerical data is typically stored in computer systems as a base-2 representation of the number. For example, the two byte integer 63119d (herein d indicates decimal notation, h indicates hexadecimal, b indicates binary notation) may be represented in a computer""s binary memory as the binary number 1100000110001011b, usually stored as two eight-bit bytes, 11000001b-10001011b (or C1h-8Bh or 193d-139d).
Many variations however are known regarding representing numerical values in binary systems are also known. One important representation is known as xe2x80x9c2""s complement notation.xe2x80x9d In this scheme, all numbers have a sign bit associated with them. Positive numbers are represented as a sign bit (e.g. 0) and the binary value of the number. Negative numbers are represented as follows: (1) take the absolute value of the number, (2) perform a bit-wise inverse of the absolute value, (3) add xe2x80x9c1xe2x80x9d, (4) include the sign bit. Thus, in 8-bit 2""s complement notation, with the leftmost bit the sign bit, 8d is represented as 00001000b and xe2x88x928d is represented as 11111000b.
A difficulty can arise when it is desired to convert a binary number to a form where it can be easily displayed in another base system, such as decimal. In many application, an information handling routine must convert from the binary-stored number to a series or string of character codes. Character codes are usually necessary for displays and/or display logic routines, printing and/or printing logic, keyboard or keypad editing, and other computer applications such as speech generation, word processing, etc. All of the applications typically require numerical data stored as binary to be first translated into a character code strings representing the number.
Known and commonly used character codes include ASCII and EBCDIC. ASCII, for example, requires generally seven bits (eight bits for various extended ASCII schemes) to designate each character, including each decimal character. ASCII is an acronym of American Standard Code for Information Interchange. The unextended code assigns the letters of the alphabet, decimal digits from 0 to 9 and some additional symbols a binary number of 7 bits, putting the 8th bit in its off state or 0. This way each letter, digit or special character occupies one byte in the computer memory.
In ASCII for example, the two-byte integer value 63179d is encoded as five integers (such as, 36h 33h 31h 37h 39h.) In ASCII, decimal places and sign bits are also generally converted to character codes: for example, the value xe2x88x9263179d is encoded as seven integer values, such as 2Dh 36h 33h 2Eh 31h 37h 39h.)
Other character codes are known. EBCDIC is an IBM adopted from punched card codes in the early 1960s and is still used on some mainframes. It exists in at least six versions and has features such as non-contiguous letter sequences, control code values from 0 to 63, and the absence of several ASCII punctuation marks.
The Baudot Code is another example code that was used extensively in telegraph systems. It is a five bit code and using five bits allowed 32 different characters. To accommodate all the letters of the alphabet and numerals, two of the 32 combinations were used to select alternate character sets. Each character is preceded by a start bit, and followed by a stop bit. It is an asynchronous code, and thus suited for low speed data communication.
While these codes present some different issues in converting between binary-encoded values, the overall problem remains the same. For simplicity, the present discussion will concentrate on conversion of binary encoded numbers to ASCII, though the present invention can be used to convert to other encoding schemes.
Translating from a binary-encoded number to a decimal character code representation in most computer systems is a processor-intensive task. One method is to translate each decimal digit separately from the left, by dividing the original number by the largest power of 10 that is less than the original number. The whole number result (also referred to as the quotient) is then looked up in a table or combined with a value to give the ASCII representation of that number. Then the same operation is performed on the remainder, and the process repeats until character codes for all the digits are determined.
Using the 63179 number above as an example, this prior art method could proceed as follows:
1. Determine the largest exponential of 10 less than the number=10000.
2. 63179/10000, has a whole number result 6 (table lookup or for ASCII add 30h)xe2x86x9236h.
3. Multiply the whole number result (6) and the divisor (10000)=60000.
4. Subtract that number from the original number (63179xe2x88x9260000=3179).
5. Repeat steps 1 through 4 until all digits are decoded, as follows:
6. Determine the largest exponential of 10 less than the number=1000.
7. 3179/1000, has a whole number result 3xe2x86x9233h.
8. Multiply the whole number result (3) and the new divisor (1000)=30000.
9. Subtract that number from the original number (3179xe2x88x923,000=179).
10. Determine the largest exponential of 10 less than the number=100.
11. 179/100, has a whole number result 1xe2x86x9231h.
12. Whole number result (1)* the divisor (100)=100.
13. 179xe2x88x92100=79.
14. 79/10 has a whole number result 7xe2x86x9237h.
15. Determine the largest exponential of 10 less than the number=10.
16. 7*10=70.
17. 79xe2x88x9270=9.
18. STOP when the subtraction result is less than ten and lookup or add that result: 9xe2x86x9239h.
19. Concatenate the resulting character codes: 36h 33h 31h 37h 39h.
An alternative method that is more condensed to express is to translate each decimal digit starting from the right, by dividing the original number by 10, and using the modulo operator to look up in a table or combined with a value to give the ASCII representation of that number. Then the same operation is performed on the result, and the process repeats until character codes for all the digits are determined. Using the 63179 number above as an example, this prior art method could be written as follows:
1. Set original number n=63179.
2. n modulo 10=9 (table lookup or for ASCII add 30h)xe2x86x9239h.
3. set n=n/10=6317.
4. Repeat steps 1 and 2 until n less than 10.
5. Lookup or add final result: 6xe2x86x9236h.
6. Concatenate the resulting character codes: 36h 33h 31h 37h 39h.
While this form, using the modulo operator, is much shorter to express, the computer operations necessary to perform the modulo are generally similar, if not longer and more complex, to the first example.
While these processes may appear simple when described using the decimal representation of the numbers, in fact the binary arithmetic calculations necessary to perform these operations are very processor intensive. In particular, divisions of binary numbers, particularly floating point numbers, can be very slow.
Converting Floating Point Numbers
Decoding a signed and/or a floating-point number requires some additional steps: (1) For signed numbers, in one example prior art method, the sign of negative numbers is first stored, then the number is converted to a positive value (which may involve a 2""s complement conversion) and the general procedure described above is performed; (2) For floating point numbers, further steps may be needed to determine the correct decimal point location and to convert the floating point number to the correct integer value before converting the binary integer value to character codes. These steps vary depending on the particular floating point encoding) scheme used in a particular system.
The present invention in various embodiments entails a method and/or apparatus and/or digital logic circuit for more quickly determining the character codes (such as ASCII or EBSIDIC character codes) for a binary-represented numerical value.
It will be understood from the teachings herein, that in specific embodiments, the present invention allows avoiding many of the divisions that can be necessary when converting numerically encoded numbers to character codes (such as ASCII). The present invention, according to specific embodiments, recognizes that processor costs of doing such divisions are very high, though the size of the divisor is generally irrelevant in terms of speed. In some situations, larger divisors actually are operated on faster than smaller.
The invention and various specific aspects and embodiments will be better understood with reference to the following drawings and detailed descriptions. For purposes of clarity, this discussion refers to devices, methods, and concepts in terms of specific examples. However, the invention and aspects thereof may have applications to a variety of types of devices and systems. It is therefore intended that the invention not be limited except as provided in the attached claims.
Furthermore, it is well known in the art that logic systems and methods such as described herein can include a variety of different components and different functions in a modular fashion. Different embodiments of the invention can include different mixtures of elements and functions and may group various functions as parts of various elements. For purposes of clarity, the invention is described in terms of systems that include many different innovative components and innovative combinations of innovative components and known components. No inference should be taken to limit the invention to combinations containing all of the innovative components listed in any illustrative embodiment in this specification.
The functional aspects of the invention that are implemented on a computer, as will be understood from the teachings herein, may be implemented or accomplished using any appropriate implementation environment or programming language, such as C, C++, Cobol, Pascal, Java, Java-script, assembly or machine code programming, custom logic circuits, etc. All references, publications, patents, and patent applications cited herein are hereby incorporated by reference in their entirety for all purposes.